用来存储数据的最基本的的结构有数组和链表两种，其他结构都是在这两种基础之上的复用与衍生。当用户进行输入时，输入可能有一定的规律，更大的可能性是输入的数据具有很大的随机性，采用数组进行存储的话，索引是一个很大的问题，因为数据的类型不一定为整数；如果采用链表，查找时必须进行遍历，对性能有很大的影响。但我们希望能找到这样的结构，不仅查找时有很高的效率，而且适用于多种结构。

幸运的是现在已经有很多这样的结构了，比如二叉搜索平衡树（红黑树、SB树等）以及这篇文章提到的hashTable。

hashTable希望提供常数时间的基本操作。

当我们要存储一定量（设为N）的数据（设为int类型）时，最先想到的是创建一个大小为N * T的数组，然后将数据依次放入空间（1放入array[0]，2数据放在array[1]。。。）。但这样会有两个问题：如果N * T的值太大，我们可能没有这么大的空间供使用；数据不是数字，也没有数字类型的标号（比如数据的类型可能是字符串），就没有办法作为数组的索引。

其中索引问题不难解决，我们可以把字符编码，然后用一些数学公式得出索引值。

第一个问题就需要用到哈希函数了。

哈希函数其实就是一种映射函数，将大数映射为小数（0 -- N - 1之间）的函数。使用哈希函数可能会碰到一个问题，不同的元素可能会被映射到相同的位置，也就是“碰撞”，解决碰撞的方法有很多种，包括线性探测、二次探测、开链等做法。这些做法的效率与